package Maze;

    use strict;
    use warnings;

    my @Instances = ();

    sub new {
        my ($Caller, %args) = (@_);
        my $Class = ref $Caller || $Caller;

        my $self = bless { }, $Class;

        if (exists $args{cols}) {
            $self->{num_cols} = $args{cols};    }
        else {
            $self->{num_cols} = 3;    }

        if (exists $args{rows}) {
            $self->{num_rows} = $args{rows};    }
        else {
            $self->{num_rows} = 3;    }

        $self->{num_verts} = ($self->{num_rows} * $self->{num_cols}) - 1;

        if (exists $args{goal} && $args{goal} <= $self->{num_verts}) {
            $self->{goal} = $args{goal};    }
        else {
            $self->{goal} = 0;    }

        if (exists $args{start}) {
            if ($args{start} <= $self->{num_verts}) {
                $self->{start} = $args{start};    }    }
        else {
            $self->{start} = $self->{num_verts};    }

        # Existing keys of %{ $self->{edges}{a_vertex} }   are the added successors for that vertex.
        # Each value corresponds to a list of the form [action, cost];
        $self->{edges} = { };
        for my $vertex (0..$self->{num_verts}) {
            $self->{edges}{$vertex} = { };    }

        $self->{connected} = 0;
        $self->{components} = undef;
        $self->{costfunction} = 1;

        push @Instances, $self;

        return $self;    }


    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    my $dispatch = { string => \&toString,
                     0      => 'w',
                     1      => 'e',
                     2      => 's',
                     3      => 'n',
                   };

    sub toString {
        my ($list, %args) = (@_);
        if ((map{$_} keys %args) == 0 || not defined $args{sorted}) {
            die "Maze::toString error: You need to specify sorted => 0 or 1.\n";    }
        return "[".join(', ', sort{$a<=>$b} @{$list})."]" if $args{sorted} != 0;
        return "[".join(', ', @{$list})."]";    }

    sub getNext {
        my $self = shift;
        my $start = shift;
        return sub {
            my $curr = $start;
            return $curr + 1;    }  }

    sub getConnectedComponents {
        my ($self, %args) = (@_);
        my $function;

        if ((map{$_} keys %args) == 0 || not defined $args{format}) {
            die "Maze::getConnectedComponents error: You need to specify format => 'string' or 'list'.\n";    }

        my @vertices = map{ $_ } 0..$self->{num_verts};
        my @components = ();
        while (@vertices) {
            my $current = shift @vertices;
            my @inSameComp = $self->getOneComponent($current);
            push @components, [@inSameComp];
            for my $vertex (@{ $components[-1] }) {
                @vertices = grep{ $_ != $vertex } @vertices;    }  }
        if ($args{format} ne 'list') {
            my $componentString = "";
            for my $component (@components) {
                $componentString .= $dispatch->{string}->($component, sorted => 1)." ";   }
            return $componentString;    }
        else {
            return (@components);    }  }

    sub makeConnected {
        my $self = shift;
        my $cost = $self->{costfunction};
        my @components = $self->getConnectedComponents(format=>'list');
        @components = sort{ scalar(@$a) <=> scalar(@$b) } @components;
        CHECKER: for (my $comp_index = 0; $comp_index < $#components; $comp_index++) {
            for my $vertex (@{ $components[$comp_index] }) {
                my @adjacents = $self->getAdjacents($vertex);
                for my $adjacent (@adjacents) {
                    if ($adjacent->[0] >= 0 && $adjacent->[0] <= $self->{num_verts}) {
                        if ((grep{$_ == $adjacent->[0]} @{ $components[$comp_index] }) == 0) {
                            $self->addEdge($vertex, $adjacent->[0], $adjacent->[1], $cost);
                            MERGER: for (my $checker = 0; $checker < $#components; $checker++) {
                                if ($checker == $comp_index) {
                                    next MERGER;    }
                                if ((grep{$_ == $adjacent->[0]} @{ $components[$checker] }) >= 1) {
                                    my $merger = splice(@components, $checker, 1);
                                    push(@{ $components[$comp_index] }, @{$merger});    }  }
                            next CHECKER;    }  }  }  }  }  }

    sub getAdjacents {
        my $self = shift;
        @_ == 1 or die "Maze::getAdjacents error: Need 1 vertex as argument.\n";
        my $vertex = shift;
        my $vertexCoord = $self->getPosition($vertex);
        $vertexCoord =~ s!^\[(.*)\]$!$1!;
        my ($vertex_x, $vertex_y) = split(', ', $vertexCoord);
        my @possibles = ($vertex - 1, $vertex + 1, $vertex + $self->{num_cols}, $vertex - $self->{num_cols});
        my @adjacents;
        my $direction = 0;
        for my $possible (@possibles) {
            my $coordinate = $self->getPosition($possible);
            if ($coordinate ne '[-1, -1]') {
                if ($direction <= 1) {
                    my $possibleCoord = $self->getPosition($possible);
                    $possibleCoord =~ s!^\[(.*)\]$!$1!;
                    my ($possible_x, $possible_y) = split(', ', $possibleCoord);
                    if ($possible_y == $vertex_y) {
                        push @adjacents, [$possible, $dispatch->{$direction}];    }  }
                $direction++;    }  }
        return (@adjacents);    }

    sub getOneComponent {
        my $problem = shift;
        my $root = shift;
        my %explored = ();
        my @component = ();
        my @frontiers = ();
        my @successors;

        push @frontiers, $root;
        while (@frontiers) {
            my $u = shift @frontiers;
            push @component, $u unless grep{$_ == $u} @component;
            $explored{$u} = 1;
            @successors = $problem->getSuccessors($u);
            for my $index (0..$#successors) {
                if (not defined $explored{ $successors[$index] }) {
                    push @frontiers, $successors[$index];    }  }  }
        return (@component);    }

    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    sub getStartState {
        my $self = shift;
        return $self->{start};    }

    sub setGoalState {
        my $self = shift;
        @_ == 1 or die "Maze::setGoalState error: Need 1 vertex as argument.\n";
        my $goalVertex = shift;
        $self->{goal} = $goalVertex;    }

    sub getGoalState {
        my $self = shift;
        my (%args) = (@_) if @_;
        if (exists $args{coords} && $args{coords} == 1) {
            return $self->getPosition($self->{goal});    }

        return $self->{goal};    }

    sub isGoalState {
        my $self = shift;
        @_ == 1 or die "Maze::isGoalState error: Need 1 vertex as argument.\n";
        my $vertex = shift;
        return $vertex == $self->{goal};    }

    sub getVertices {
        my $self = shift;
        return "{".join(', ', sort{$a <=> $b} map{$_} keys %{ $self->{edges} })."}"    }

    sub getSuccessors {
        my $self = shift;
        my $vertex = shift;

        my @successors = ();
        for my $i (0..$self->{num_verts}) {
            if ($self->hasEdge($vertex, $i)) {
                push @successors, $i;    }  }
        return (@successors);    }

    sub getPosition {
        my $self = shift;
        @_ == 1 or die "Maze::getPosition error: Need 1 vertex as argument.\n";
        my $vertex = shift;
        return '[0, 0]' if $vertex == 0;
        return '[-1, -1]' if ($vertex < 0 || $vertex > $self->{num_verts});
        my ($col, $row) = (1, 0);
        for my $v (1..$self->{num_verts}) {
            if ($v % $self->{num_cols} == 0) {
                $row++;
                $col = 0;    }
            return $dispatch->{string}->([$col, $row], sorted => 0) if $v == $vertex;
            $col++;    }  }

    sub getVertex {
        my $self = shift;
        @_ == 2 or die "Maze::getVertex error: Need an x, y coordinate.\n";
        my ($col, $row) = (@_);
        if ($row == 0) {
            return $col;    }
        elsif ($row > 0) {
            return (($row * $self->{num_cols}) + $col);    }
        else {
            return -1;    }  }

    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    sub addRows {
        my $self = shift;
        @_ == 1 or die "Maze::addRows error: Need 1 number as argument.\n";
        my $num = shift;
        my $old = $self->{num_verts};

        $self->{num_verts} += ($self->{num_cols} * $num);
        $self->{num_rows} += $num;    }

    sub getNumRows {
        my $self = shift;
        return $self->{num_rows};    }

    sub getNumCols {
        my $self = shift;
        return $self->{num_cols};    }

    sub getNumVerts {
        my $self = shift;
        return $self->{num_verts};    }

    sub addEdge {
        my $self = shift;
        @_ == 4 or die "Maze::addEdge error: Need 2 vertices, an action and a cost as arguments.\n";
        my ($vertex1, $vertex2, $action, $cost) = (@_);
        my $reverseAction = $self->reverseAction($action);

        if ($reverseAction =~ m/^Invalid$/) {
            die "Maze::addEdge error: An action needs to be one of the following: n, s, w, e.\n";    }

        # %{ $self->{edges}{vertex} } keys, are all the defined edges of that vertex to that key.
        if (not defined $self->{edges}{$vertex1}{$vertex2}) {
            $self->{edges}{$vertex1}{$vertex2} = [$action, $cost];
            $self->{edges}{$vertex2}{$vertex1} = [$reverseAction, $cost];    }  }

    sub hasEdge {
        my $self = shift;
        @_ == 2 or die "Maze::hasEdge error: Need 2 vertices as arguments.\n";
        my ($vertex1, $vertex2) = (@_);
        if (defined $self->{edges}{$vertex1}{$vertex2}) {
            return 1;    }
        else {
            return 0;   }  }

    sub reverseAction {
        my $self = shift;
        my $action = shift;

        if ($action =~ m/^n$/) {
            return "s";    }
        elsif ($action =~ m/^s$/) {
            return "n";    }
        elsif ($action =~ m/^w$/) {
            return "e";    }
        elsif ($action =~ m/^e$/) {
            return "w";    }
        else {
            return 'Invalid';
        }  }

    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#
    #*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*#

    sub buildMaze {
        my $self = shift;
        my $limit = shift;
        my $fact;
        my $cost = $self->{costfunction};
        my $numCols = $self->{num_cols};
        my $numRows = $self->{num_rows};
        my $numVerts = $self->{num_verts};
        my ($leftNeighbour, $rightNeighbour, $bottomNeighbour, $upNeighbour);

        my $row;
        for (my $current = 0; $current < $numVerts-2;) {
            $row = 0;
            ($leftNeighbour, $rightNeighbour, $bottomNeighbour, $upNeighbour) =
            ( $current - 1 ,   $current + 1 , $current + $numCols, $current - $numCols);

            #if ($leftNeighbour >= 0 && $leftNeighbour <= (($numCols*$row)+$numCols-1)) {
            if ($leftNeighbour >= 0 && $current % 3 != 0) {
                $fact = int rand $limit;
                if ($fact != 0) {
                    $self->addEdge($current, $leftNeighbour, 'w', $cost);    }  }
            if ($rightNeighbour <= $numVerts && $rightNeighbour % $numCols != 0) {
                $fact = int rand $limit;
                if ($fact != 0) {
                    $self->addEdge($current, $rightNeighbour, 'e', $cost);    }  }
            if ($row < $numRows-1) {
                $fact = int rand $limit;
                if ($fact != 0) {
                    $self->addEdge($current, $bottomNeighbour, 's', $cost);    }  }
            if ($row > 0) {
                $fact = int rand $limit;
                if ($fact != 0) {
                    $self->addEdge($current, $upNeighbour, 'n', $cost);    }  }
            $current++;
            if ($current % 3 == 0) {
                $row++;    }  }  }

    sub printMaze {
        my $maze = shift;
        my $numRows = $maze->getNumRows();
        my $numCols = $maze->getNumCols;
        my $numVerts = $maze->getNumVerts();
        my $goal = $maze->getGoalState();#coords=>1);

        for (my $i = 0; $i < $numCols; $i++) {
            ($i =~ m/\b\d{1}\b/) ? print " $i " : print " $i";    }
        print "\n";
        for (my $i = 0; $i < $numCols; $i++) {
            print "+--";    }
        print "+\n";

        my $vertex = 0;
        my $row = 0;
        my $coln = 0;

        while ($vertex < $numVerts) {
            print "|";
            for (my $col = 0; $col < $numCols; $col++) {
                if ($maze->hasEdge($vertex, $vertex + 1) == 1) {
                    if ($maze->getVertex($coln, $row) == $goal) {
                    #if ("($coln, $row)" =~ m/$goal/) {
                        print "XX ";    }
                    else {
                        print "   ";    }  }
                else {
                    if ($maze->getVertex($coln, $row) == $goal) {
                    #if ("($coln, $row)" =~ m/$goal/) {
                        print "XX|";    }
                    else {
                        print "  |";    }  }
                $vertex++;
                $coln++;    }
            print "\n|";
            $coln = 0;
            my $rcount = $vertex - $numCols;
            if ($row == $numRows - 1) {
                for (my $i = 0; $i < $numCols; $i++) {
                    print "--+";    }
                print "\n";    }
            else {
                for ( my $col = 0; $col < $numCols; $col++ ) {
                    if ($maze->hasEdge($rcount, $rcount + $numCols) == 1) {
                        print "  +";    }
                    else {
                        print "--+";    }
                    $rcount++;
                    $coln++;    }  }
            print "\n";
            $row++;
            $coln = 0;    }  }

    sub getMazeString {
        my $string = "";
        my $maze = shift;
        my $numRows = $maze->getNumRows();
        my $numCols = $maze->getNumCols;
        my $numVerts = $maze->getNumVerts();
        my $goal = $maze->getGoalState();#(coords=>1);

        for (my $i = 0; $i < $numCols; $i++) {
            ($i =~ m/\b\d{1}\b/) ? ($string .= " $i ") : ($string .= " $i")    }
        $string .= "\n";
        for (my $i = 0; $i < $numCols; $i++) {
            $string .= "+--";    }
        $string .= "+\n";

        my $vertex = 0;
        my $row = 0;
        my $coln = 0;

        while ($vertex < $numVerts) {
            $string .= "|";
            for (my $col = 0; $col < $numCols; $col++) {
                if ($maze->hasEdge($vertex, $vertex + 1) == 1) {
                    if ($maze->isGoalState($maze->getVertex($coln, $row))) {
                        $string .= "XX ";    }
                    else {
                        $string .= "   ";    }  }
                else {
                    if ($maze->isGoalState($maze->getVertex($coln, $row))) {
                        $string .= "XX|";    }
                    else {
                        $string .= "  |";    }  }
                $vertex++;
                $coln++;    }
            $string .= "\n|";
            $coln = 0;
            my $rcount = $vertex - $numCols;
            if ($row == $numRows - 1) {
                for (my $i = 0; $i < $numCols; $i++) {
                    $string .= "--+";    }
                $string .= "\n";    }
            else {
                for ( my $col = 0; $col < $numCols; $col++ ) {
                    if ($maze->hasEdge($rcount, $rcount + $numCols) == 1) {
                        $string .= "  +";    }
                    else {
                        $string .= "--+";    }
                    $rcount++;
                    $coln++;    }  }
            $string .= "\n";
            $row++;
            $coln = 0;    }

            return "$string";    }

    # Class end
    1;
